package org.example.top40;

public class main24 {
    //最长递增子序列是
    //输入：nums = [10,9,2,5,3,7,101,18]
    //输出：4 [2,3,7,101]，因此长度为 4
    //思路：dp[i]以nums[i]结尾的最长递增长度
    //fori,j j找出[0,i)区间最大的序列 只要满足nums[i]>nums[j] 就可以赋值
    //max(dp[i],dp[j]+1) 每forj完就比较一次最大res 最后返回res
    public static void main(String[] args) {
        int[] nums={10,9,2,5,3,7,101,18};
        int len=nums.length;
        int[] dp=new int[len];
        int res=0;
        for (int i = 0; i < len; i++) {
            dp[i]=1;
            for (int j = 0; j < i; j++) {
                if (nums[i]>nums[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            if(res<dp[i]){
                res=dp[i];
            }
        }
        System.out.println(res);
    }
}
